# 112.路径总和
# 给你二叉树的根节点root和一个表示目标和的整数targetSum 。判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和
# targetSum 。如果存在，返回true ；否则，返回false 。
# 叶子节点是指没有子节点的节点。
#
# 示例1：
# 输入：root = [5, 4, 8, 11, null, 13, 4, 7, 2, null, null, null, 1], targetSum = 22
# 输出：true
#
# 示例2：
# 输入：root = [1, 2, 3], targetSum = 5
# 输出：false
# 解释：树中存在两条根节点到叶子节点的路径：
# (1 --> 2): 和为3
# (1 --> 3): 和为4
# 不存在sum = 5的根节点到叶子节点的路径。
#
# 示例3：
# 输入：root = [], targetSum = 0
# 输出：false
# 解释：由于树是空的，所以不存在根节点到叶子节点的路径。

import sys
sys.setrecursionlimit(1000000)  # 例如这里设置为一百万

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


class Solution:
    def hasPathSum(self, root: [TreeNode], targetSum: int) -> bool:
        # 1.确定入参和返回值
        def traver(root,count)->bool:
            # 2.确定终止条件
            if (not root.left) and (not root.right):
                if count == 0:
                    return True
                else:
                    return False
            # 3.处理逻辑
            if root.left:
                count -= root.left.val
                istrue = traver(root.left,count)
                if istrue:
                    return True
                count += root.left.val
            if root.right:
                count -= root.right.val
                istrue = traver(root.right,count)
                if istrue:
                    return True
                count += root.right.val
            return False
        if not root:
            return False
        return traver(root,targetSum-root.val)


if __name__ == '__main__':
    a31 = TreeNode(15)
    a32 = TreeNode(7)
    a22 = TreeNode(20,a31,a32)
    a21 = TreeNode(9)
    a11 = TreeNode(3,a21,a22)
    tmp = Solution()
    aaaa = 238
    res = tmp.hasPathSum(a11,aaaa)
    # targetSum = 23
    # res = tmp.hasPathSum(a11,targetSum)
    print(res)



